package com.zcoj.util;

import org.springframework.stereotype.Component;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
 * @author chenbin
 * @version 1.0
 * @description: TODO
 * @date 2023/6/5 16:48
 */

@Component
public class WinnowingCodeSimilarity {
    private  final int K = 5; // K-gram长度
    private  final int WINDOW_SIZE = 4; // 窗口大小
    private  final int BASE = 101; // 哈希计算的基数

//    public static void main(String[] args) {
//        String code1 = "在程序设计类比赛中在线评测系统是对参赛选手的程序进行评测的在线系统，它利用黑盒测试原理进行自动化测试来判断程序是否正确";
//        String code2 = "在线评测系统是一种在编程竞赛中用来评测参赛程序的在线系统，也可用于平时练习";
//
//        List<Integer> hashList1 = generateHashList(code1);
//        List<Integer> hashList2 = generateHashList(code2);
//
//        Map<Integer, Integer> fingerprint1 = generateFingerprint(hashList1);
//        Map<Integer, Integer> fingerprint2 = generateFingerprint(hashList2);
//
//        double similarity = calculateSimilarity(fingerprint1, fingerprint2);
//        System.out.println("Similarity: " + similarity);
//    }

    public double Similarity(String code1,String code2){

        List<Integer> hashList1 = generateHashList(code1);
        List<Integer> hashList2 = generateHashList(code2);

        Map<Integer, Integer> fingerprint1 = generateFingerprint(hashList1);
        Map<Integer, Integer> fingerprint2 = generateFingerprint(hashList2);

        return calculateSimilarity(fingerprint1, fingerprint2);

    }


    private  List<Integer> generateHashList(String code) {
        List<Integer> hashList = new ArrayList<>();

        for (int i = 0; i <= code.length() - K; i++) {
            String kgram = code.substring(i, i + K);
            int hash = generateHash(kgram);
            hashList.add(hash);
        }

        return hashList;
    }

    private  int generateHash(String kgram) {
        int hash = 0;

        for (int i = 0; i < K; i++) {
            hash += kgram.charAt(i) * Math.pow(BASE, K - 1 - i);
        }

        return hash;
    }

    private  Map<Integer, Integer> generateFingerprint(List<Integer> hashList) {
        Map<Integer, Integer> fingerprint = new HashMap<>();

        for (int i = 0; i <= hashList.size() - WINDOW_SIZE; i++) {
            List<Integer> window = hashList.subList(i, i + WINDOW_SIZE);
            int minHash = getMinHash(window);
            fingerprint.put(i + WINDOW_SIZE - 1, minHash);
        }

        return fingerprint;
    }

    private  int getMinHash(List<Integer> window) {
        int minHash = Integer.MAX_VALUE;

        for (int hash : window) {
            if (hash < minHash) {
                minHash = hash;
            }
        }

        return minHash;
    }

    private  double calculateSimilarity(Map<Integer, Integer> fingerprint1, Map<Integer, Integer> fingerprint2) {
        int intersectionCount = 0;
        int unionCount = fingerprint1.size() + fingerprint2.size();

        for (int position : fingerprint1.keySet()) {
            if (fingerprint2.containsKey(position)) {
                if (fingerprint1.get(position).equals(fingerprint2.get(position))) {
                    intersectionCount++;
                }
            }
        }

        return (double) (2 * intersectionCount) / unionCount;
    }
}

